package leetcode_501_600;

import java.util.Arrays;

public class LeeCode_516 {
    public static void main(String[] args) {
        System.out.println(longestPalindromeSubseq("bbbab"));
        System.out.println(longestPalindromeSubseq("cbbd"));
        System.out.println(longestPalindromeSubseq("abcabcabcabc"));
    }
    private static int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] memo = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(memo[i], -1);
        }
        return dfs(s, 0, n - 1,  memo);
    }
    private static int dfs(String s, int i, int j, int[][] memo){
        if (i == j)
            return 1;
        if (i > j)
            return 0;
        if (memo[i][j] != -1){
            return memo[i][j];
        }
        if (s.charAt(i) == s.charAt(j)) {
            return memo[i][j] = dfs(s, i + 1, j - 1,  memo) + 2;
        }else {
            return memo[i][j] = Math.max(dfs(s, i + 1, j,  memo), dfs(s, i, j - 1, memo));
        }
    }
}
